%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% input
\KwIn{Positive integer $n$ and integer $N$ with $0 \leq N \leq \binom{n}{2}$.}
%%
%% output
\KwOut{A random graph from $G(n,N)$.}
\BlankLine
%%
%% algorithm body
$G \assign \overline{K_n}$\;
$E \assign \left\{e_0, e_1, \dots, e_{\binom{n}{2} - 1}\right\}$\;
\For{$i \assign 0, 1, \dots, N - 1$}{
  $r \assign$ draw uniformly at random from $\left\{0, 1, \dots, \binom{n}{2} - 1\right\}$\;
  \While{\rm $e_r$ is an edge of $G$}{
    $r \assign$ draw uniformly at random from $\left\{0, 1, \dots, \binom{n}{2} - 1\right\}$\;
  }
  add edge $e_r$ to $G$\;
}
\Return $G$\;
